CS254 Spring 2003Practice Midterm 2

The practice midterm is below. Here are some facts about the actual midterm: (a) The midterm will be in class . (b) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (c) You should bring photo ID. (d) There will be more than one version of the test. Each version will be of comparable difficulty. (e) If your cell-phone or beeper goes off you will be excused from the test at that point and graded on what you have done till your excusal. (f) One problem (less typos) on the actual test will be from the practice test.

1. The monotone circuit value problem (MCVP) is the circuit value problem restricted to circuits without NOT gates. Show MCVP is P-complete with respect to logspace reductions.

2. A database table is arranged into columns called attributes and has rows of data. Given two sets of attributes X and Y, a functional dependency X-->Y holds between them if whenever we fix the values of X and look at rows in the table with those values of X they will all have the same values of Y. Given a table T and a set of functional dependencies FD a key is a minimal set X that fixes the set of all the attributes in the table. Show the problem of figuring out whether a table T with functional dependencies FD has a key of size less that k is NP-complete.

3. Prove there are no P-complete problems under linear time reductions.

4. A k-coloring of a graph G=(V,E) is a function f: V--> 1...k such that if (i,j) is an edge in E then f(i) =/= f(j). Show the problem of determining whether a graph G has a subgraph of m vertices (that has all the edges from the original graph on these vertices) which is 3-colorable is NP-complete.

5. Let F be a Boolean expression and let t be a truth assignment for a set X of some but not neccessarily all of F's variable. Consider the problem of determining whether every satisfying assignment of F assigns the variables in X the same way t did. Show this problem is coNP-complete.

6. Describe what a Pratt certificate for primality consists of.

7. Suppose we are given a black box that solves the CLIQUE problem and that a turing machine can use this black box by writing an instance of CLIQUE to a special tape and entering a new state called QUERY. In one time step the black box outputs after this instance on this special tape the symbol y if the answer to the clique problem was YES and n if the query did not make sense or if the answer to the CLIQUE problem was no. Show how to use the blackbox to give a p-time algorithm to find a CLIQUE of size n/2 in a graph of size n if such a CLIQUE exists.

8. Let X be a random variable assuming only nonnegative values. Prove Markov's Inequality (a variation on Lemma 11.2): Pr(X >= t) <= E(X)/t.

9. Show that PP is close under logspace many-one reductions.

10. Let PPTIME(f(n)) be those language in PP accepted in time f(n). Show PPTIME(n) is strictly contained in PPTIME(n³).